package violentRecursion;

import org.junit.Test;

/*
 *@description 不同路径
 *@author hkfan
 *@version 1.0
 *@create 2025/5/16 16:21
 */
public class LeetCode_62 {
    int sum=0;

    @Test
    public void test(){
        System.out.println(uniquePaths(3, 7));
    }

    public int uniquePaths(int m, int n) {
        sum=0;
        solution_2(m,n,1,1);
        return sum;
    }

    /**
     * @description 暴力递归
     * @author hkfan
     * @time 2025/5/16 16:26
     */
    private void solution_1(int m, int n, int x, int y) {
        //1. 条件判断
        if (x<1||x>n){
            return ;
        }
        if (y<1||y>m){
            return ;
        }
        if (x==n&&y==m){
            sum++;
        }
        //2. 递归
        solution_1(m,n,x+1,y);
        solution_1(m,n,x,y+1);
    }

    /**
     * @description 动态规划
     * @author hkfan
     * @time 2025/5/16 16:26
     */
    private void solution_2(int m, int n, int x, int y) {
        //1. 定义变量
        int res=0;
        if (m>n){
            solution_2(n,m,x,y);
            return;
        }
        int[][] dp = new int[m+1][n+1];
        //2. 对dp设置初值
        for (int j = 0; j <= n; j++) {
            dp[m][j]=1;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][n]=1;
        }
        //3. 对dp进行填充
        for (int i = m-1; i >= 1; i--) {
            for (int j = n-1; j >=1; j--) {
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        sum = dp[1][1];

    }


}
